# -*- coding=utf-8 -*-
# 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式
# 示例 1:
# 输入: num1 = "2", num2 = "3"
# 输出: "6"

# 示例 2:
# 输入: num1 = "123", num2 = "456"
# 输出: "56088"

# 说明：
# num1 和 num2 的长度小于110
# num1 和 num2 只包含数字 0-9
# num1 和 num2 均不以零开头，除非是数字 0 本身
# 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理

# # 渣到不行，仅仅战胜6%
# class Solution(object):
#     def multiply(self, num1, num2):
#         """
#         :type num1: str
#         :type num2: str
#         :rtype: str
#         """
#         if(len(num1) == 1 and int(num1) == 0):
#             return "0";
#         if(len(num2) == 1 and int(num2) == 0):
#             return "0";

#         rtn = "";
#         for i in range(0, len(num2)):
#             result = self.mul(num1, num2[len(num2) - i - 1]);
#             result = result + "0" * i;
#             rtn = self.add(rtn, result);
#         return rtn;

#     def add(self, s_num_p1, s_num_p2):
#         long_length = len(s_num_p1) if len(s_num_p1) > len(s_num_p2) else len(s_num_p2);
#         s_num_p1 = s_num_p1[::-1];
#         s_num_p2 = s_num_p2[::-1];
#         rtn = "";
#         carry = 0;
#         for i in range(0, long_length):
#             num_p1 = 0;
#             num_p2 = 0;
#             if(i < len(s_num_p1)):
#                 num_p1 = int(s_num_p1[i]);
#             if(i < len(s_num_p2)):
#                 num_p2 = int(s_num_p2[i]);
#             result = num_p1 + num_p2 + carry;
#             rtn = str(result % 10) + rtn;
#             carry = result // 10;
#         if carry:
#             rtn = str(carry) + rtn;
#         return rtn;

#     def mul(self, s_long_num, s_signal_num):
#         signal_num = int(s_signal_num);
#         s_long_num = s_long_num[::-1];

#         rtn = "";
#         carry = 0;

#         for i in range(0, len(s_long_num)):
#             num = int(s_long_num[i]);
#             result = num * signal_num + carry;
#             rtn = str((result % 10)) + rtn;
#             carry = result // 10;
#         if carry != 0:
#             rtn = str(carry) + rtn;
#         return rtn;








# 思路
# 1、分割字符串
# 2、字符串 各位依次相乘 结果放置在对应的位置上
# 3、对应位置依次相加把进位加到下一位上
# eg: 25 * 25
# 1、[2, 5] * [2, 5]
# 2、[0, 4, 20, 25]
# 3、[0, 6, 2, 5]
class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        if(num1 == "0" or num2 == "0"):
            return "0";

        split_num_p1 = [int(i) for i in num1];
        split_num_p2 = [int(i) for i in num2];
        split_rtn_list = [0 for i in range(0, len(num1) + len(num2))];
        for i in range(0, len(split_num_p1)):
            for j in range(0, len(split_num_p2)):
                split_rtn_list[-1 - i - j] += split_num_p1[-1 - i] * split_num_p2[-1 - j];

        carry = 0;
        for i in range(0, len(split_rtn_list)):
            result = split_rtn_list[-1 - i] + carry;
            split_rtn_list[-1 - i] = result % 10;
            carry = result // 10;

        begin = 0;
        for i in range(0, len(split_rtn_list)):
            if(split_rtn_list[i] == 0):
                continue;
            begin = i;
            break;

        rtn = "";
        for i in range(begin, len(split_rtn_list)):
            rtn += str(split_rtn_list[i]);

        return rtn;

t = Solution();
print t.multiply("125", "125");